機器學習1-決策樹及隨機森林
林嶔 (Lin, Chin)
Lesson 19
機器學習概論(1)
- 從這節課開始，我們將踏入機器學習的領域。機器學習的目標是在用過往的資料預測未來，我們將由簡單至困難，並跟著科學發展的歷程一起學習這些方法。
– 機器學習的方法分為無監督學習法及監督學習法，我們的課程內容著重在監督學習法，其主要目標是想透過原始資料的特徵(feature)，並經過模型進行預測(預測的outcome可以為連續或是類別)。
- 我們已經知道，若我們希望準確的預測一件事情的發生，那麼最準確的方式是了解了變量之間的關係，並設計出優美的關係方程式，如此便是最準確的方法。
– 然而，有時候受限於研究的限制，我們沒有辦法將它們之間的關係描述得很精準，舉例來說，我們如何做手寫數字的辨識?
機器學習概論(2)
- 我們以一個最簡單的多分類問題來看，假定每個樣本有2個特徵，因此每個點能打在座標平面上，而假定現在有3個類別分別標以不同的顏色：
data(iris)
plot(iris[,1], iris[,2], col = as.factor(iris[,5]), pch = 19,
xlab = "Sepal Length", ylab = "Sepal Width")
- 那麼我們舉最常用的4種機器學習方法(決策樹/邏輯斯回歸/支持向量機/隨機森林)對上面的圖形分類，結果會大致如下：
- 根據我們的觀察，我們可以發現邏輯斯回歸的致命缺陷，也就是他僅能處理『線性可分割』的問題，如果問題是『線性不可分割』，那邏輯斯回歸將無法非常好的進行分類。
機器學習概論(3)
- 儘管如此，我們還是先從邏輯斯回歸開始，在之前我們已經學習過了使用函數「glm」可以進行邏輯斯回歸，但他的限制有點多(如僅能做2類及樣本數必須超過變項數)，我們使用一個優化的套件進行邏輯斯回歸：
– 事實上，這個套件做的是「Penalized」logistic regression。
#Split data
set.seed(0)
Train.sample = sample(1:150, 100, replace = FALSE)
Train.data = iris[Train.sample,]
Test.data = iris[-Train.sample,]
#Train a model
library(glmnet)
glm.model = glmnet(y = Train.data[,5],
x = as.matrix(Train.data[,1:4]),
family = "multinomial",
lambda = 0.1)
#Predict
pred.test = predict(glm.model, as.matrix(Test.data[,1:4]))
pred.y = max.col(pred.test[,,1])
#Comparision
table(pred.y, Test.data[,5])
##
## pred.y setosa versicolor virginica
## 1 18 0 0
## 2 0 14 1
## 3 0 1 16
練習-1
- 讓我們來面對一個複雜一點的線性不可分割的問題，請你再試試邏輯斯回歸的效果：
– 請在這裡下載MNIST的手寫數字資料
- 這份資料是Kaggle上面讓世界各地的好手們比賽他們如何做手寫數字辨識，資料結構為一個785欄的資料集
– 其中第一欄是標籤，也就是0至9
– 第二欄開始是一個28*28圖片的像素，範圍大小是0-255
- 我們試著讀取檔案，並且利用他來呈現幾個手寫數字吧！
DAT = read.csv("data/train.csv")
#Split data
set.seed(0)
Train.sample = sample(1:nrow(DAT), nrow(DAT)*0.6, replace = FALSE)
Train.X = DAT[Train.sample,-1]
Train.Y = DAT[Train.sample,1]
Test.X = DAT[-Train.sample,-1]
Test.Y = DAT[-Train.sample,1]
#Display
library(imager)
par(mar=rep(0,4), mfcol = c(4, 4))
for (i in 1:16) {
plot(NA, xlim = 0:1, ylim = 0:1, xaxt = "n", yaxt = "n", bty = "n")
img = as.raster(t(matrix(as.numeric(Train.X[i,])/255, nrow = 28)))
rasterImage(img, -0.04, -0.04, 1.04, 1.04, interpolate=FALSE)
text(0.05, 0.95, Train.Y[i], col = "green", cex = 2)
}
- 看來你很清楚X與Y之間的關係了，試著用函數「glmnet」進行預測吧！
– 使用Train.X與Train.Y建立模型，在以模型預測Test.X，並將預測結果與Test.Y進行比較
## Test.Y
## pred.y 0 1 2 3 4 5 6 7 8 9
## 1 1123 1 99 15 106 29 320 93 124 59
## 2 60 1819 385 1346 179 646 186 186 908 294
## 3 3 0 193 6 8 13 6 1 12 4
## 4 9 3 20 129 67 153 30 12 80 84
## 7 36 5 360 30 19 26 911 0 10 0
## 8 1 0 1 53 79 113 0 991 51 557
## 10 431 23 598 163 1148 571 208 470 490 644
## Training accuracy rate = 0.2122222
## Testing accuracy rate = 0.2145238
決策樹(1)
- 邏輯斯迴歸由於僅能處理「線性可分割」的問題，故效果不太好，我們需要學習其他工具來處理「線性不可分割」問題。
– 最簡單的監督機器學習法是決策樹，決策樹牽涉到了最少的數學，僅僅是使用電腦大量運算來進行分類。
- 決策樹的原理是，在大量的變項(X)中找出「一個」能對「該樣本」有「最大分類效果」的規則，並按規則持續把樣本分割，直到再也找不出規則為止！
決策樹(2)
- 讓我們來試著用iris的資料實作決策樹吧，我們先設計一個簡單的邏輯，我們找出每個變項的最佳切點(切割後以費雪檢定進行檢定，p value最小為最佳切點)，接著比較各變項最佳切點的卡方值，選擇一個最好的分類方法
data(iris)
#Split data
set.seed(0)
Train.sample = sample(1:150, 100, replace = FALSE)
Train.data = iris[Train.sample,]
Test.data = iris[-Train.sample,]
#Find optimal cut-points
optimal.cut_points = data.frame(var = colnames(Train.data)[1:4],
cut = numeric(4),
pval = numeric(4))
for (i in 1:4) {
unique.values = unique(sort(Train.data[,i]))
chisq.list = numeric(length(unique.values)-1)
for (j in 1:length(chisq.list)) {
potiantal.cut_points = (unique.values[j] + unique.values[j+1])/2
names(chisq.list)[j] = potiantal.cut_points
X = Train.data[,i] > potiantal.cut_points
Y = Train.data[,5]
chisq.list[j] = fisher.test(X, Y)$p.value
}
optimal.cut_points[i,2] = names(chisq.list)[which.min(chisq.list)]
optimal.cut_points[i,3] = min(chisq.list)
}
print(optimal.cut_points)
## var cut pval
## 1 Sepal.Length 5.55 7.257472e-16
## 2 Sepal.Width 3.15 2.248091e-09
## 3 Petal.Length 2.45 6.992396e-27
## 4 Petal.Width 0.8 6.992396e-27
- 看來使用Petal.Length以及使用Petal.Width進行分類的效果一樣好，我們來試試看用套件做的結果如何。
決策樹(3)
- 事實上決策樹因為對於「最大分類效果」的定義有相當多種，所以有非常多不同種類的決策樹，由於我們剛剛的結果是以卡方檢定的結果為標準，故我們這裡使用conditional inference tree作驗證
library(party)
tree.model = ctree(formula = Species ~ ., data = Train.data)
plot(tree.model)
- 結果看起來好像不太一樣，但其實是一樣的，因為>1.9和>2.45意思是相同的。
## [1] 1.2 1.2 1.3 1.3 1.3 1.3 1.3 1.4 1.4 1.4 1.4 1.4 1.4 1.4 1.4 1.4 1.5
## [18] 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.6 1.6 1.6 1.6 1.6 1.7 1.9 1.9 3.0 3.3
## [35] 3.3 3.5 3.6 3.7 3.8 3.9 3.9 4.0 4.0 4.0 4.1 4.1 4.2 4.2 4.2 4.3 4.4
## [52] 4.4 4.4 4.5 4.5 4.5 4.5 4.5 4.5 4.6 4.7 4.7 4.7 4.8 4.8 4.8 4.8 4.9
## [69] 4.9 5.0 5.0 5.0 5.1 5.1 5.1 5.2 5.2 5.3 5.3 5.4 5.4 5.5 5.5 5.6 5.6
## [86] 5.6 5.6 5.7 5.7 5.8 5.8 5.8 5.9 6.1 6.1 6.3 6.4 6.6 6.7 6.9
決策樹(4)
#Predict
pred.y = predict(tree.model, Test.data[,1:4])
#Comparision
table(pred.y, Test.data[,5])
##
## pred.y setosa versicolor virginica
## setosa 18 0 0
## versicolor 0 15 1
## virginica 0 0 16
- 好像比邏輯斯迴歸更準了，我們試試他在手寫數字分類的效果吧！
練習-2
- 手寫數字分類實在太難寫出他的規則了，而且是一個線性不可分割的問題，邏輯斯回歸的表現很不好，讓我們試試看決策樹吧！
– 想想決策樹的運算過程，你應該可以想像他要一陣子才能算完，你可能需要等2-3分鐘。
## Training accuracy rate = 0.7399206
## Testing accuracy rate = 0.7175595
## Test.Y
## pred.y2 0 1 2 3 4 5 6 7 8 9
## 0 1527 3 127 118 12 251 79 11 54 18
## 1 3 1535 29 41 18 33 13 92 50 26
## 2 14 135 1186 91 23 26 122 35 86 14
## 3 2 28 8 1006 6 119 5 7 11 14
## 4 2 1 15 10 979 10 42 18 10 14
## 5 31 4 19 172 54 691 23 42 101 150
## 6 37 5 115 12 41 56 1298 3 64 14
## 7 14 9 35 15 45 65 19 1353 21 86
## 8 15 107 72 77 50 68 38 29 1206 32
## 9 18 24 50 200 378 232 22 163 72 1274
- 這個結果似乎跟邏輯斯迴歸的結果有很大的不同，預測能力有了明顯的長進，感覺到決策樹的威力了嗎?
隨機森林(1)
- 決策樹確實有能力解決線性不可分割問題，如同我們剛剛所見我們發現了他對於手寫數字的預測能力遠遠超過了邏輯斯回歸。
– 但他有一個重要的缺陷，就是我們Training sample是一次抽樣的結果，而這個樣本一定存在了一些抽樣誤差造成的特色與母體未必相同，我們有沒有可能因為這個錯誤的特色導致了決策樹陷入「局部極值」?
- 當然是有可能的，所以學者們想出了隨機森林來解決這個問題，他的做法是把原來的樣本「隨機的」抽取一小部分當新樣本，並依此新樣本作出一棵決策樹，然後再重複抽樣產生第二棵樹，依此類推…
– 接著，假設我們成功的製造了100棵小樹，要預測的時候就將這樣本經過這100棵樹，並請這100棵樹投票看看他們預測這個樣本的結果。
– 這樣的操作在數學上的意義，就像我們在做梯度下降法時從100個「隨機的起始點」開始疊代程序，即使我們無法判斷「全局極值」在哪個點，我們應該也能透過這100個方程式的投票獲得更準確的結果！
隨機森林(2)
- 讓我們來試試使用套件完成隨機森林樹吧，但因為要產生很多小樹運算量驚人，我們僅設置20棵樹。
data(iris)
#Split data
set.seed(0)
Train.sample = sample(1:150, 100, replace = FALSE)
Train.data = iris[Train.sample,]
Test.data = iris[-Train.sample,]
#Load library
library(randomForest)
#Modeling
rf.model = randomForest(formula = Species ~ ., data = Train.data, ntree = 20)
#Predict
pred.y = predict(rf.model, Test.data)
table(pred.y, Test.data[,5])
##
## pred.y setosa versicolor virginica
## setosa 18 0 0
## versicolor 0 15 1
## virginica 0 0 16
練習-3
- 把隨機森林應用在手寫數字分類上吧，但因為運算量的問題，請你設置20棵樹就好了。
– 僅僅20棵樹大約就花了2-3分鐘的時間計算，回家以後你可以設置多一點樹看看結果！
## Training accuracy rate = 0.9998413
## Testing accuracy rate = 0.9485119
## Test.Y
## pred.y2 0 1 2 3 4 5 6 7 8 9
## 0 1635 1 10 4 4 15 11 4 4 11
## 1 0 1821 3 3 4 0 4 8 12 4
## 2 1 5 1570 30 6 2 2 22 15 9
## 3 4 2 14 1616 0 40 1 2 31 24
## 4 0 3 10 2 1505 3 5 14 9 29
## 5 3 4 6 30 0 1446 11 1 25 12
## 6 9 3 10 2 15 17 1620 0 10 2
## 7 1 2 11 16 5 1 0 1665 5 26
## 8 10 8 19 24 15 17 7 8 1547 15
## 9 0 2 3 15 52 10 0 29 17 1510
- 準確度真是有驚人的提升，在測試資料上已經有95%的準確度了。
– 但遺憾的是在訓練資料已經100%能預測，看來沒有上升空間了，但真的是這樣嗎?
小結
本週我們帶領大家一起學會了決策樹及隨機森林，他們在面對一些較複雜的問題時效能遠遠超過了邏輯斯回歸。
儘管我們不清楚X與Y實際上的關係，這兩個機器學習的方法還是有效的協助我們預測出量的結果。
事實上，隨機森林還並非Tree-based model的最終型態，在2003年以後出現的梯度提升機(Gradient Boosting Machine)是一個比隨機森林更強的分類器
– 在R裡面最好用的套件是xgboost，如果你想深入學習請參考範例
– 他的概念是在建構樹的過程中改變樣本權重，使每一棵樹的變化性更大。
– 在Kaggle比賽中，使用xgboost建立的梯度提升機是各項賽事中的常勝軍，幾乎所有的比賽中都看的到他的身影。